// 二叉树：树中每个节点最多只能有两个子节点
// 前中后序遍历
console.log("==== 前序遍历");
//  根左右
//  1. 访问根节点
// 2. 对根节点的左子树进行先序遍历
// 3. 对根节点的右子树进行先序遍历
const preorder = (root) => {
  if (!root) {
    return;
  }
  console.log(root.val);
  preorder(root.left);
  preorder(root.right);
};
console.log("==== 中序遍历");
// 右根左
// 1. 对根节点的左子树进行中序遍历
// 2. 访问根节点
// 3. 对根节点的右子树进行中序遍历

const inorder = (root) => {
  if (!root) {
    return;
  }
  inorder(root.left);
  console.log(root.val);
  inorder(root.right);
};

// 左右根
// 1. 对根节点的左子树进行后序遍历
// 2. 对根节点的右子树进行后序遍历
// 3. 访问根节点

const postorder = (root) => {
  if (!root) {
    return;
  }
  postorder(root.left);
  postorder(root.right);
  console.log(root.val);
};

// ================ 非递归版本

const preorderNoRecursion = (root) => {
  if (!root) {
    return;
  }
  const stack = [root];
  while (stack.length) {
    const n = stack.pop();
    console.log(n.val);
    if (n.right) {
      stack.push(n.right);
    }
    if (n.left) {
      stack.push(n.left);
    }
  }
};

const inorderNoRecursion = (root) => {
  if (!root) {
    return;
  }
  const stack = [];
  let p = root;
  while (stack.length || p) {
    while (p) {
      stack.push(p);
      p = p.left;
    }
    const n = stack.pop();
    console.log(n.val);
    p = n.right;
  }
};

const postNoRecursion = (root) => {
  if (!root) {
    return;
  }
  const stack = [];
  const outputStack = [];
  while (stack.length) {
    const n = stack.pop();
    outputStack.push(n);
    if (n.left) {
      stack.push(n.left);
    }
    if (n.right) {
      stack.push(n.right);
    }
  }
  while (outputStack.length) {
    const n = outputStack.pop();
    console.log(n.val);
  }
};
